\paragraph{Nettoyage de la matrice}
~\\

A présent pour cette structure:
  \begin{center}
  (\ .\ (\ .\ .\ )\ )\ .\ (\ )\ \ 11
  \end{center}
~\\

La matrice\footnote{Matrice non réduite pour une meilleure vision du problème} correspondante est:
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.2]{../imports/last_match2.png}
\caption{\label{matrice_n_n} Matrice pour traiter les redondances}
\end{center}
\end{figure}
\\
\newpage
Cependant la matrice indique qu'on doit étudier:
\\
\begin{itemize}
 \item La structure 1 entre les positions 11 et 17: $A$
  \item La structure 1 entre les positions 13 et 16: $B$
  \item La structure 1 entre les positions 19 et 20: $C$ .
\end{itemize}
~\\

Mais l'étude de la sous-structure $A$ implique celle de $B$ car elle est incluse dans $A$, on doit alors, en définitive, considérer les structures $A$ et $C$.

Pour cela, après avoir rempli la matrice, je décide de parcourir celle-ci pour supprimer les sous-structures qui sont incluses dans d'autre qu'on traite déjà. J'enrichis alors ma structure de données, utilisée pour traiter une séquence au format dot-bracket, en ajoutant une variable $\gamma$, initialisée à $0$, qui contiendra la position du dernier nucleotide apparié rencontré.

Pour être sûr de rencontrer le plus grand appariement lors du parcours de la matrice il faut faire une exploration verticale, étant donné qu'on soit sûr que $i<j$. Ainsi si on rencontre une case $i,j$ non vide on regarde la valeur de $j$\footnote{appariement courant} si $j<\gamma$ alors on supprime l'indice de la séquence de la case. Sinon on la garde et on met à jour $\gamma$ afin d'avoir le plus grand appariement par l'affectation: $\gamma \leftarrow j$.


On a au final:
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.15]{../imports/matrice_finale2.png}
\caption{\label{matrice_n} Matrice finale}
\end{center}
\end{figure}
\\
\newpage
\paragraph{L'algorithme complet}
~\\

Pour résumer :

Soient:
\begin{itemize}
\item[.] $n$ : le nombre de structure secondaire prédite pas RNALfold pour une séquence donnée
\item[.] $mat$ : la matrice de calcul de taille $i.b$
\item[.] $f$ : Une fonction qui prend en paramètre l'indice d'une structure, une position dans celle-ci et retourne la taille de la structure la plus grande dans laquelle elle est contenue.
~\\
\\
Pour illustrer, si on considère la structure k : 
\begin{verbatim}
(  .  (  (  (  .  .  )  )  )  )    2  
2  3  4  5  6  7  8  9  10 11 12
\end{verbatim}
~\\Pour la sous-structure entre les positions 5 et 10: $f(k,5) = 12-2 + 1 = 11$
\\Pour la sous-structure entre les positions 6 et 9:$f(k,6) = 12-2 + 1 = 11$
\\$f(k,2) = 0$ car la sous structure entre les positions 2 et 10 est égale à la structure k.
\end{itemize}
~\\

Ainsi:\\
\begin{lstlisting}
  
\end{lstlisting}
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{../imports/organigramme1.png}
\caption{\label{matrice_n} Algorithme de traitement des redondances}
\end{center}
\end{figure}
~\\

\newpage

Les structures redondantes enfin traitées, on peut alors commencer la recherche de tige boucle, précurseurs de microARN.
